package com.arraylist.p4;

public class DoubleLinkedList{

    //首节点
    private Node headNode;
    //尾结点
    private Node lastNode;

    private int size;

    public int size(){
        return size;
    }

    private static class Node{

       private Object data;

       private Node pre;

       private Node next;

       public Node(Object data){
          this.data=data;
       }
    }

    /**
     *添加元素
     * @param element
     */
    public void add(Object element){

        Node node=new Node(element);
        if(headNode==null){
           headNode=node;
           lastNode=node;
        }
        else {
            lastNode.next=node;
            node.pre=lastNode;
            lastNode=node;
        }
        size++;
    }

    /**
     * 根据序号获得元素
     * @param index
     */
    public Object get(int index){

        if(index<0||index>size){
            throw new IndexOutOfBoundsException("索引不合法:"+index);
        }
        Node node = node(index);
        return node.data;
    }

    /**
     * 根据序号删除元素
     * @param index
     */
    public void remove(int index){

        if(index<0||index>size){
            throw new IndexOutOfBoundsException("序号不合法:"+index);
        }

        //删除节点在首节点
        if(index==0){
            Node nextNode=headNode.next;
            headNode.next=null;
            if(nextNode!=null){
                nextNode.pre=null;
            }
            headNode=nextNode;
        }
        else if(index==size-1){
            Node preNode=lastNode.pre;
            preNode.next=null;
            lastNode.pre=null;
            lastNode=preNode;
        }
        //删除节点在中间
        else{
            //删除节点
            Node delNode = node(index);
            Node preNode=delNode.pre;
            Node nextNode=delNode.next;
            preNode.next=nextNode;
            nextNode.pre=preNode;
            delNode.pre=null;
            delNode.next=null;

        }
         size--;
    }

    /**
     * 根据序号添加元素
     * @param index
     * @param element
     * @return
     */

    public void add(int index,Object element){

        if(index<0||index>size){
            throw new IndexOutOfBoundsException("序号不合法"+index);
        }
        Node node = new Node(element);
        //在首节点添加元素
        if(index==0){
          node.next=headNode;
          headNode.pre=node;
          headNode=node;
        }
        //在尾节点添加元素
        else if(index==size){
            add(element);
            return;
        }
        else{
            //插入节点的对应的节点对象
            Node curNode = node(index);
            //插入位置前一个节点对象
            Node preNode=curNode.pre;
            preNode.next=node;
            node.pre=preNode;
            node.next=curNode;
            curNode.pre=node;
        }
        size++;
    }

    /**
     * 根据序号获得节点对象
     * @param index
     * @return
     */
    private Node node(int index){
        //查找的节点在前半区
        if(index<size/2){
            Node nextNode=headNode;
            for(int i=0;i<index;i++){
               nextNode=nextNode.next;
            }
            return nextNode;
        }
        //查找的节点在后半区
        else{
            Node preNode=lastNode;
            for(int i=size-1;i>index;i--){
                preNode=preNode.pre;
            }
            return preNode;
        }
    }


}
